package com.coder.algorithm.offer_2;

import java.util.Locale;

/**
 * 剪绳子
 *
 * @author yuhushuan
 * @date 2020/6/11 10:28
 */
public class _14_1_CuttingRope {
    public static void main(String[] args) {
        // 功能测试（绳子的初始长度大于5）
        // 边界值测试（绳子的初始长度分别为0、1、2、3、4）

        for (int len = 0; len < 10; ++len) {
            System.out.println(String.format(Locale.getDefault(), "长度为 %d 的绳子最大乘积是 %d",
                    len, maxProduct_solution1(len)));
            System.out.println(String.format(Locale.getDefault(), "长度为 %d 的绳子最大乘积是 %d",
                    len, maxProduct_solution2(len)));
        }
    }

    /**
     * 动态规划
     *
     * @param length
     * @return
     */
    private static int maxProduct_solution1(int length) {
        if (length < 2) {
            return 0;
        } else if (length == 2) {
            return 1;
        } else if (length == 3) {
            return 2;
        }
        int[] products = new int[length + 1];
        // 当 length >= 4 时，各段乘积最大值
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;

        int max = 0;
        for (int i = 4; i <= length; ++i) {
            max = 0;
            for (int j = 1; j <= i / 2; ++j) {
                int product = products[j] * products[i - j];
                if (max < product) {
                    max = product;
                }
            }
            products[i] = max;
        }
        return max;
    }

    private static int maxProduct_solution2(int length) {
        if (length < 2) {
            return 0;
        } else if (length == 2) {
            return 1;
        } else if (length == 3) {
            return 2;
        }

        // 尽可能多地剪去长度为 3 的绳子段
        int timesOf3 = length / 3;
        // 当绳子最后剩下的长度为 4 的时候，不能再剪去长度为 3 的绳子段。
        if (length % 3 == 1) {
            // 此时更好的方法是把绳子剪成长度为 2 的两段，因为 2*2 > 3*1
            timesOf3 -= 1;
        }
        int timesOf2 = (length - timesOf3 * 3) / 2;

        return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timesOf2);
    }
}
